// 最经典的一种随机洗牌算法，来自Fisher-Yates
// 实现思路：
// 从数组的最后一位开始迭代
// 将迭代到的元素和一个随机位置交换，这个随机位置要求比当前位置小
// 这个机制从数学上保证了每个元素随机过的位置不会再随机一次

export function shuffle<T>(arr: T[]): T[] {
    for (let i = arr.length - 1; i >= 0; i--) {
        const randomIndex = Math.floor(Math.random() * (i + 1));
        swap(arr, i, randomIndex);
    }
    return arr;
}

// 交换函数
function swap<T>(arr: T[], index1: number, index2: number): void {
    let temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
}


// 测试用例
console.log(shuffle([1, 2, 3, 4, 5]));
console.log(shuffle([1, 2, 3, 4, 5]));
console.log(shuffle([1, 2, 3, 4, 5]));
console.log(shuffle([1, 2, 3, 4, 5, 6]));
console.log(shuffle([1, 2, 3, 4, 5, 6, 7, 7]));
